1. Field of the Invention
This invention relates to an analog signal characterizer for executing a functional transformation, such as fast Fourier transform (FFT) or fast Hadmard transform (FHT), and more particularly to an analog signal characterizer for converting an analog serial signal into discrete parallel signals to execute the functional transformation in parallel through butterfly operations.
2. Related Art
For functional transformation of a signal sequence having discrete numerical values, N-point discrete Fourier transform (DFT) is known, which is expressed by formula (1). ##EQU1##
The N-point DFT (i.e., DFT for signal sequence of length N) requires N.sup.2 times multiplication. Fast Fourier transform (FFT) is an algorithm for performing the same operations all at once to reduce the operation time and efficiently execute DFT. Arithmetic operation of FFT will be explained using an eight (8) point (N=2.sup.3 =8) DFT as an example. In formula (1), where the N value is 8 (N=8), assume that the N/2 DFT values of the X.sub.n even terms are B.sub.0, B.sub.1, B.sub.2 and B.sub.3, and the N/2 DFT values of the x.sub.n odd terms are C.sub.0, C.sub.1, C.sub.2 and C.sub.3, then formula (2) is obtained. EQU X.sub.0 =B.sub.0 +C.sub.0 W.sub.8.sup.0 ( 2) EQU X.sub.1 =B.sub.1 +C.sub.1 W.sub.8.sup.1 EQU X.sub.2 =B.sub.2 +C.sub.2 W.sub.8.sup.2 EQU X.sub.3 =B.sub.3 +C.sub.3 W.sub.8.sup.3 EQU X.sub.4 =B.sub.4 +C.sub.4 W.sub.8.sup.4 =B.sub.0 -C.sub.0 W.sub.8.sup.0 EQU X.sub.5 =B.sub.5 +C.sub.5 W.sub.8.sup.5 =B.sub.1 -C.sub.1 W.sub.8.sup.1 EQU X.sub.6 =B.sub.6 +C.sub.6 W.sub.8.sup.6 =B.sub.2 -C.sub.2 W.sub.8.sup.2 EQU X.sub.7 =B.sub.7 +C.sub.7 W.sub.8.sup.7 =B.sub.3 -C.sub.3 W.sub.8.sup.3
FIG. 1 shows the rotational factor W.sub.N.sup.k of the formula (2). The rotational factor W.sub.N.sup.k is a complex number for the angle 2.pi.k/N as expressed by formula (3). The last four equations for X.sub.4 to X.sub.7 of formula (2) are obtained by replacing W.sub.8.sup.4 to W.sub.8.sup.7 by -W.sub.8.sup.0 to -W.sub.8.sup.3 using the characteristics of the rotational factor shown in FIG. 1. EQU W.sub.N.sup.k =-W.sub.N.sup.(k.+-.N/2) ( 3)
Formula (2) results from time division of the 8-point DFT into two 4-point DFT groups, namely, even terms X.sub.0, X.sub.2, X.sub.4 and X.sub.6, and odd terms X.sub.1, X.sub.3, X.sub.5 and X.sub.7. This signal flow is shown in FIG. 2. Suppose the DFT of the even terms among X.sub.0, X.sub.2, X.sub.4 and X.sub.6 (i.e., terms X.sub.0 and X.sub.4) are D.sub.0 and D.sub.1, and the DFT of the odd terms among X.sub.0, X.sub.2, X.sub.4 and X.sub.6 (i.e., terms X.sub.2 and X.sub.6) are E.sub.0 and E.sub.1. Then B.sub.0 is the sum of D.sub.0 and the product of E.sub.0 and W.sub.8.sup.0. Similarly, B.sub.1 is the sum of D.sub.1 and the product of E.sub.1 and W.sub.8.sup.2. B.sub.2 is the sum of D.sub.0 and the product of E.sub.0 and W.sub.8.sup.4 (-W.sub.8.sup.0) . B.sub.3 is the sum of D.sub.1 and the product of E.sub.1 and W.sub.8.sup.6 (-W.sub.8.sup.2) . These are expressed by formula (4). The blocks of N/2-point DFT (4-point DFT) shown in FIG. 2 is redrawn as FIG. 3 realizing the signal flow of formula (4). EQU B.sub.0 =D.sub.0 +E.sub.0 W.sub.8.sup.0 ( 4) EQU B.sub.1 =D.sub.1 +E.sub.1 W.sub.8.sup.2 EQU B.sub.2 =D.sub.0 +E.sub.0 W.sub.8.sup.4 =D.sub.0 -E.sub.0 W.sub.8.sup.0 EQU B.sub.3 =D.sub.1 +E.sub.1 W.sub.8.sup.6 =D.sub.1 -E.sub.1 W.sub.8.sup.2 EQU C.sub.0 =F.sub.0 +G.sub.0 W.sub.8.sup.0 EQU C.sub.1 =F.sub.1 +G.sub.1 W.sub.8.sup.2 EQU C.sub.2 =F.sub.0 +G.sub.0 W.sub.8.sup.4 =F.sub.0 -G.sub.0 W.sub.8.sup.0 EQU C.sub.3 =F.sub.1 +G.sub.1 W.sub.8.sup.6 =F.sub.1 -G.sub.1 W.sub.8.sup.2
The pairs of D.sub.0 and D.sub.1, E.sub.0 and E.sub.1, F.sub.0 and F.sub.1, and G.sub.0 and G.sub.1 are N/4 DFT (2-point DFT), respectively. Therefore, formula (4) can be expressed as formula (5), in view of W.sub.8.sup.0 =1 and W.sub.8.sup.4 =-1. EQU D.sub.0 =x.sub.0 +x.sub.4 W.sub.8.sup.0 =x.sub.0 +x.sub.4 ( 5) EQU D.sub.1 =x.sub.0 +x.sub.4 W.sub.8.sup.4 =x.sub.0 -x.sub.4 EQU E.sub.0 =x.sub.2 +x.sub.6 W.sub.8.sup.0 =x.sub.2 +x.sub.6 EQU E.sub.1 =x.sub.2 +x.sub.6 W.sub.8.sup.4 =x.sub.2 -x.sub.6 EQU F.sub.0 =x.sub.1 +x.sub.1 W.sub.8.sup.0 =x.sub.1 +x.sub.5 EQU F.sub.1 =x.sub.1 +x.sub.1 W.sub.8.sup.4 =x.sub.1 -x.sub.5 EQU G.sub.0 =x.sub.3 +x.sub.7 W.sub.8.sup.0 =x.sub.3 +x.sub.7 EQU G.sub.1 =x.sub.3 +x.sub.7 W.sub.8.sup.4 =x.sub.3 -x.sub.7
FIG. 4 shows a signal flow according to the butterfly operations of formulae (2) to (5). Eight discrete signals x.sub.0 to x.sub.7 are obtained by dividing the analog serial signal in the time domain and sampling the divided signals. The discrete signals x.sub.0 to x.sub.7 are transformed to eight new frequency signals X.sub.0 to X.sub.7.
In FIG. 4, addition operations are performed at the intersections of the signal lines. Among the intersections, negative addition operations (subtraction) are performed at the points indicated by "-1". At the points marked with W.sub.N.sup.k, the coefficients W.sub.N.sup.k are multiplied to the corresponding signal. D.sub.0, D.sub.1, E.sub.0, E.sub.1, F.sub.0, F.sub.1, G.sub.0, G.sub.1, B.sub.0, B.sub.1, B.sub.2, B.sub.3, C.sub.0, C.sub.1, C.sub.2 and C.sub.3 are the intermediate calculation results of the signals X.sub.0 to X.sub.7.
For example, addition of signals x.sub.0 and x.sub.4 results in D.sub.0, while subtraction of x.sub.4 from x.sub.0 results in D.sub.1, which confirms the relationship shown in formula (5). Also, B.sub.0 is obtained by adding D.sub.0 to the product of E.sub.0 and W.sub.8.sup.0, while B.sub.1 is obtained by adding D.sub.1 to the product of E.sub.1 and W.sub.8.sup.2, which confirms the relationship shown in formula (4). X.sub.0 is obtained by adding B.sub.0 to the product of C.sub.0 and W.sub.8.sup.0, while X.sub.1 is obtained by adding B.sub.1 to the product of C.sub.1 and W.sub.8.sup.1, which confirms the relationship shown in formula (2).
In order to output the signals X.sub.0 to X.sub.7 in this order, the input serial signal must be rearranged into the prescribed order prior to the butterfly operations (along the crossing signal lines of FIG. 4). Without rearrangement, the output signals are not well-ordered, as shown in the signal flow of FIG. 5. However, it is known that the signal flow of FIG. 4 and that of FIG. 5 perform an equivalent functional transformation with only a difference in the order of input and output signals.
Although an FFT operation was used for the above example, fast Hadmard transform (FHT) can be performed if the weighting coefficient (rotational factor W.sub.N.sup.k) is shaped into two values of .+-.1 using the function shown in formula (6). EQU sgn(x)=1(x&gt;0) sgn(x)=-1(x&lt;0) (6)
Conventionally, digital-type signal characterizers are used to perform a functional transformation, such as FFT or FHT. However, to perform parallel calculations with a digital-type signal characterizer, many multipliers are necessary, making the circuit of the signal characterizer large. A signal characterizer performing sequential FFT or FHT operations could be realized by a DSP (digital signal processor) with software such as assembler. However, in this case, large numbers of butterfly operations must be performed in series, rather than in parallel. Therefore, when a long serial signal is input, huge numbers of operations must be executed, requiring a very long time period.
This invention was conceived to overcome the above issues. Therefore, the object of the invention is to realize quick butterfly operations through parallel processes by rearranging the order of the input signal sequence or the output signal sequence, and to construct the signal characterizer using analog circuits.
It is another object of the invention to provide a signal characterizer which reduces power consumption by adapting capacitors as impedances in the analog circuit.